class IndexWrongFullExcetion extends RuntimeException{
    public IndexWrongFullExcetion() {
    }

    public IndexWrongFullExcetion(String message) {
        super(message);
    }
}

//用穷举的方式实现无头单向非循环链表
public class MySingLeList {
    //一个结点内部类
    static class ListNode{
        public int value;//定义存放数据的域
        public ListNode next;//定义存放下一个结点地址的域

        //构造方法
        public ListNode(int value){
            this.value = value;
        }
    }

    //创建一个链表的头部，来作为链表的头结点
    public ListNode head;//不初始化，默认的地址时空

    //创建一个方法，实现5个结点的链表
    public void createList() {
        ListNode listNode1 = new ListNode(12);
        ListNode listNode2 = new ListNode(23);
        ListNode listNode3 = new ListNode(34);
        ListNode listNode4 = new ListNode(45);
        ListNode listNode5 = new ListNode(56);

        //使这5个结点链接起来
        listNode1.next = listNode2;//将第2个结点的地址给第1个结点
        listNode2.next = listNode3;//将第3个结点的地址给第2个结点
        listNode3.next = listNode4;//将第4个结点的地址给第3个结点
        listNode4.next = listNode5;//将第5个结点的地址给第4个结点

        //将头结点指向第1个结点，head结点里存了第1个结点的地址
        this.head = listNode1;
    }

    //打印链表的数据
    public void disPlay() {
        //为了head不会向后移动直至指向null，导致头结点消失，定义一个临时变量来代替head移动
        ListNode cur = this.head;
        //不能是cur.next != null，因为这样会少打印一个结点的数据
        while(cur != null) {
            //输出链表的元素
            //cur此时标识的是头结点
            System.out.print(cur.value + " ");//打印头结点数据域的元素
            cur = cur.next;//将头结点指向下一个位置的结点
        }
        System.out.println();
    }

    //查找key是否在单链表中 - 存在返回true，不存在返回false
    public boolean contains(int key) {
        ListNode cur = this.head;//代替head向后移动
        while (cur != null) {
            if (cur.value == key) {
                return true;//相等返回true
            }
            //cur是此时头结点
            //cur.next的意思是找到当前cur结点的指针域
            cur = cur.next;//不相等继续找下一个结点
        }
        return false;//循环结束返回false
    }

    //头插法 - 插入结点到头部
//头插法可以不考虑表是不是null - 即使表是空的node的地址域也是null，也能找到下一个结点
    public void addStart(int data) {
        //1.定义一个要插入的结点node
        ListNode node = new ListNode(data);

        //2.让node的地址域指向原表的头结点
        node.next = this.head;

        //3.再让原表的头结点直向新表的头结点（node）
        head = node;
    }

    //尾插法 - 插入几点到尾部
    public void addEnd(int data) {
        //1.定义一个结点和cur
        ListNode cur = this.head;//代替head向后移动
        ListNode node = new ListNode(data);//新结点node
        //现在分两个情况：1.链表不为空，即链表的尾结点在最后一个结点处. 2.链表为空，即head就是尾结点.

        //2.找到尾结点 - cur指向的地址为空就是尾结点
        //情况2：链表为空
        if(cur == null) {
            this.head = node;//直接将头结点指向node结点
        }else{ //情况1：链表不为空
            while(cur.next != null) {
                cur = cur.next;//找到下一个结点
            }
            //3.此时已经找到了尾结点，可以开始将结点串联起来了
            cur.next = node;//cur的地址域指向node结点
        }
    }

    private ListNode findIndexSubOne(int index) { //查找index位置的方法
        ListNode cur = this.head;//代替head向后移动
        //index不等于0则说明还没找到index的结点
        while (index - 1 != 0) {
            cur = cur.next;//找到下一个结点
            index--;//更加接近index位置
        }
        return cur;//此时cur指向的就是index
    }

    //在链表指定位置插入一个结点
    public void addIndex(int index, int data) throws IndexWrongFullExcetion{  //index是位置，逻辑上定义的下标；data是要插入的结点
        ListNode node = new ListNode(data);//新结点node
        //下标不能是负数，不能超过表的结点数
        if (index < 0 || index > size()) {
            System.out.println("index位置不合法！！！");
            throw new IndexWrongFullExcetion("index位置不合法！！！");
        }
        if (index == 0) { //如果index在0位置则属于头插法
            addStart(data);//头插法 - 调用头插法方法
            return;
        }
        if (index == size()) {  //如果index在size()位置则属于尾插法
            addEnd(data); //尾插法 - 调用尾插法
            return;
        }

        //剩下的情况就是在中间位置插入
        //1.先让cur找到index-1的位置，即我要插入的位置
        ListNode cur = findIndexSubOne(index);//调用方法接收了cur的index结点位置
        //2.改变结点的指向来完成插入
        node.next = cur.next;//要插入结点的地址域指向index位置的下一个结点的地址域
        cur.next = node;//再将index的地址域指向node结点的数据域
    }

    private ListNode findPrevOfKey(int key) { //查找key前一个结点的方法
        ListNode cur = this.head;//代替head向后移动
        //当cur指向链表尾结点的前一个结点时整个链表就判断完了
        while (cur.next != null) {
            //cur指向的地址域，再指向这个地址的数据域里的数据
            if (cur.next.value == key) {
                return cur;//找到了key的前一个位置，此时cur就是key的前一个结点
            }
            cur = cur.next; //没找到调整

        }
        //代码走到这里肯定为空
        return null;//返回null说明没找到
    }

    //得到单链表的长度 - 结点个数
    public int size() {
        int count = 0;//计数器，统计结点的个数
        //为了head不会向后移动直至指向null，导致头结点消失，定义一个临时变量来代替head移动
        ListNode cur = this.head;
        while (cur != null) { //尾结点为null
            count++;//结点个数加1
            cur = cur.next;//头结点指向下一个结点
        }
        return count;//返回结点数
    }

    //删除第一次出现的key结点
    public void remove(int key) {
        //key不能超过表的长度
        //先找到要删除的key结点的前一个结点，然后改变这个结点的指向，使其指向key结点的后一个结点
        //链表有可能是空的 - 判断一下
        if (this.head == null) {
            return;
        }
        //第一种情况是key在头结点 - 直接向后移动
        if (this.head.value == key) {
            this.head = this.head.next;//头结点指向头结点的下一个结点
            return;
        }
        //程序走到这里说明链表不是空的，而且key不在头结点处
        ListNode cur = findPrevOfKey(key);//调用此方法后此时cur指向的是key的前一个结点
        //链表中有可能没有key结点
        if (cur == null) {
            System.out.println("链表中没有这个结点！！！");
            return;
        }
        //定义一个del结点，del是要删除的结点
        ListNode del = cur.next;//cur.next指向的是要删除的结点

        //删除
        cur.next = del.next;//当前key结点的前一个结点的地址域指向要删除结点的下一个结点的地址域
    }

    //删除所有key的结点
    public void removeAllKey(int key) {
        //链表中可能是空的
        if(this.head == null) {
            return;
        }

        ListNode cur = this.head.next;//cur指向要删除的结点
        ListNode prev = this.head;//prev指向要删除结点的前驱
        //cur不等于空则说明cur未找到尾结点，移动要继续
        while (cur != null) {
            //如果当前的cur指向的数据是我要找的key
            if (cur.value == key) {
                //改变指向删除
                prev.next = cur.next;//要删除结点的前驱的地址域指向key结点的后驱的地址域
                cur = cur.next;//要删除的结点指向它的后驱
            }else{ //若不是要找的 - 跳到下一个结点
                prev = cur;//当前cur结点的前驱指向cur指向的结点
                cur = cur.next;//当前cur结点指向它的后驱
            }
        }
        //如果链表的第一个结点是key
        if (this.head.value == key) {
            this.head = this.head.next;//将这个头结点指向它的后驱 - 然后就删除了
        }
    }

    //清空链表
    public void clear() {
        this.head = null;//将的结点置为空
    }

    public static void main(String[] args) {
        MySingLeList mySingLeList = new MySingLeList();
        //测试创建链表的方法 - 调试观看
        mySingLeList.createList();
        // 输出链表的元素
        mySingLeList.disPlay();
        //测试查找key数据是否存在 - contains(int key)
        System.out.println(mySingLeList.contains(34));//输出true
        System.out.println(mySingLeList.contains(44));//输出false

        //测试头插法
        mySingLeList.addStart(3);
        mySingLeList.addStart(2);
        mySingLeList.addStart(1);
        mySingLeList.disPlay();//打印单链表 - 结果是1 2 3 12 23 34 45 56

        //测试尾插法
        mySingLeList.addEnd(67);
        mySingLeList.addEnd(78);
        mySingLeList.addEnd(89);
        mySingLeList.disPlay();//打印此时链表结点数据 - 1 2 3 12 23 34 45 56 67 78 89

        //测试删除第一次出现的key结点的方法
        mySingLeList.remove(34);//删除表中的存放34数据的结点
        mySingLeList.disPlay();//打印当前链表的数据 - 应该输出1 2 3 4 12 23 45 56 67 78 89

    }
}
